import sys
import random

class CMapGenerator( object ):
    """ Map generator responsible for creating traversable 2d dungeon maps. """
    

    
    MAX_SPACE_SEARCH_ITERATIONS = 100

    def __init__( self , inColumns , inRows , inBorderSize ):
        """ Init map generator with a general map size. """
        self.mColumns = inColumns
        self.mRows = inRows
        self.mBorderSize = inBorderSize
        
        # Player start and exit placeholders
        self.mPlayerStart = [ 0 , 0 ]
        self.mPlayerExit = [ 0 , 0 ]
        
        # Generate a 'Full' map to 'carve out' from.
        self.mWalls = [['#' for i in range( self.mColumns )] for j in range( self.mRows )]
        
        # Establish our flood cache
        self.mFloodFillCacheX = []
        self.mFloodFillCacheY = []


    def PrintMap( self ):
        """ Print map to stdout. """
        for row in range( self.mRows ):
            sys.stdout.write('\n');
            for col in range( self.mColumns ):
                sys.stdout.write( self.mWalls[ row ][ col ] );
                
    def GetPlayerStart( self ):
        """ Accessor for player start. """
        return self.mPlayerStart
    
    def GetPlayerExit( self ):
        """ Accessor for player exit. """
        return self.mPlayerExit

    def GenerateMap( self ):
        """ Primary function. Generates a useable map. """
        
        # Add most of our wall shape
        self.AddNoise(4)
        self.DrawCorridors()
        self.Corrode(4)
        self.DrawBorder()
        
        # Add our player start and exit
        self.GetValidPlayerStart()
        self.GetValidPlayerExit()

       # self.PrintMap()
        return self.mWalls



    def AddNoise( self , noiseInfluence ):
        """ Traverse the map and add random noise. Noise influence can be total (10) or lesser (0-9)."""
        for row in range( self.mRows ):
            for col in range( self.mColumns ):
                r = random.randint( 0 , 11 - noiseInfluence )
                if( r == 0 ):
                    self.mWalls[ row ][ col ] = ' ';
                elif( r==1 ):
                    self.mWalls[ row ][ col ] = '#';
                else:
                    None

    def DrawLine( self , x1 , y1 , x2 , y2 ):
        """ 'Cut' a line out of the map. Credit to roguelikedevelopment.org for Bresenham implementation."""
        issteep = abs(y2-y1) > abs(x2-x1)
        if issteep:
            x1, y1 = y1, x1
            x2, y2 = y2, x2
        rev = False
        if x1 > x2:
            x1, x2 = x2, x1
            y1, y2 = y2, y1
            rev = True
        deltax = x2 - x1
        deltay = abs(y2-y1)
        error = int(deltax / 2)
        y = y1
        ystep = None
        if y1 < y2:
            ystep = 1
        else:
            ystep = -1
        # These values are inverted because accessing mWalls is of formwat mWalls[y][x]
        for x in range(x1, x2 + 1):
            if issteep:
                self.mWalls[ x ][ y ] = ' ';
            else:
                self.mWalls[ y ][ x ] = ' ';
            error -= deltay
            if error < 0:
                y += ystep
                error += deltax

    def DrawCorridors( self ):
        """ Draw a random number of corridors of random direction/length. """
        r = random.randint( 20 , 25 )
        for each in range(r):
            randx1 = random.randint( 0 , self.mColumns-1 )
            randy1 = random.randint( 0 , self.mRows-1 )
            randx2 = random.randint( 0 , self.mColumns-1 )
            randy2 = random.randint( 0 , self.mRows-1 )
            #print( str(randx1) + " " + str(randy1) + " " + str(randx2) + " " + str(randy2) )
            self.DrawLine( randx1 , randy1 , randx2 , randy2 )
            
    def DrawBorder( self ):
        """ Draw a border around the map. """
        for row in range( self.mRows ):
            for col in range( self.mColumns ):
                if row == 0 or row == self.mRows-1 or col == 0 or col == self.mColumns-1:
                    self.mWalls[ row ][ col ] = '#'
                    
    def FloodFill( self ,  x , y ):
        """ Fill in an open space in the map with periods. This will determine spawnable space. """
        
        # RETURN: If we are at the end of our array
        if x < 0 or x > len( self.mWalls )-1:
            return
        if y < 0 or y > len( self.mWalls[x] )-1:
            return
        
        # RETURN: If we hit a wall, return
        if self.mWalls[x][y] == '#':
            return
        
        # RETURN: If we've already flooded this cell
        for i in range( 0 , len( self.mFloodFillCacheX ) ):
            if  self.mFloodFillCacheX[i] == x and self.mFloodFillCacheY[i] == y :
                return
        
        # Add our coordinates to the flood cache
        self.mFloodFillCacheX.append( x )
        self.mFloodFillCacheY.append( y )
        
        # Debug: Fills map with stairs where fill occurs
        #self.mWalls[x][y] =  "%"
        
        # Call ourself until the job is done
        self.FloodFill( x+1 , y )
        self.FloodFill( x-1 , y )
        self.FloodFill( x , y+1 )
        self.FloodFill( x , y-1 )
        
        return
    
    def GetValidPlayerStart( self ):
        """ Gets a valid player start in the map which is determined by a 3x3 open square.
            You can set the limit on how many times you are willing to search for an empty space by adjusting MAX_SPACE_SEARCH_ITERATIONS. """
        i = 0
        while( i <= CMapGenerator.MAX_SPACE_SEARCH_ITERATIONS ):
            
            # Create a randomly generated tuple that will create a coordinate somewhere inside of our wall map
            # Starts at 1 and ends at -2 on each coord to avoid out of bounds.
            coord = ( random.randint( 1 , len( self.mWalls[0] ))-2 , random.randint( 1 , len( self.mWalls ))-2 ) 
            
            # Keep count of walls around the space. Could optimize this with buckets/comprehension.
            wallTotal = 0
            wallTotal += 1 if self.mWalls[ coord[1]-1 ][ coord[0]-1 ] == '#' else 0
            wallTotal += 1 if self.mWalls[ coord[1]-1 ][ coord[0]   ] == '#' else 0
            wallTotal += 1 if self.mWalls[ coord[1]-1 ][ coord[0]+1 ] == '#' else 0
            wallTotal += 1 if self.mWalls[ coord[1]   ][ coord[0]-1 ] == '#' else 0
            wallTotal += 1 if self.mWalls[ coord[1]   ][ coord[0]   ] == '#' else 0
            wallTotal += 1 if self.mWalls[ coord[1]   ][ coord[0]+1 ] == '#' else 0
            wallTotal += 1 if self.mWalls[ coord[1]+1 ][ coord[0]-1 ] == '#' else 0
            wallTotal += 1 if self.mWalls[ coord[1]+1 ][ coord[0]   ] == '#' else 0
            wallTotal += 1 if self.mWalls[ coord[1]+1 ][ coord[0]+1 ] == '#' else 0
            
            # If there were no walls around us, we're good.
            if( wallTotal == 0):
                self.mPlayerStart = coord
                # Draw our playerstart on map
                self.mWalls[ self.mPlayerStart[1] ][ self.mPlayerStart[0] ] = "@"
                return
            
            i += 1
            
        return
    
    def GetValidPlayerExit( self , saveExit = True ):
        """ Get a valid player exit by flood filling the player start ( call GetValidPlayerStart(...) before using this ) 
        and choosing from the filled area. This does not return a variable but populates
        the mPlayerExit variable. This method also clears the flood fill cache when done. """
        
        # First we do our flood fill so that our fill cache is populated by valid coordinates
        self.FloodFill( self.mPlayerStart[1] , self.mPlayerStart[0] )
        self.mWalls[self.mPlayerStart[1]][self.mPlayerStart[0]] = "@"
        
        # Get a random value in the range of the flood fill cache. They are both the same size so one number works.
        randValue = random.randint( 0 , len( self.mFloodFillCacheX ) )
        
        # Set our mPlayerExit
        self.mPlayerExit[0] = self.mFloodFillCacheX[randValue]
        self.mPlayerExit[1] = self.mFloodFillCacheY[randValue]
        
        # Draw our exit on the map
        if( saveExit == True ):
            self.mWalls[ self.mPlayerExit[0] ][ self.mPlayerExit[1] ] = "%"
        
        # Clear our Flood Fill Cache
        self.mFloodFillCacheX = None
        self.mFloodFillCacheY = None
        
        return
        
    def GetWallTouchingCount( self , x , y ):
        """ Return the number of adjacent walls touching the given cell. """
        wallTotal = 0;

        # Check top
        wallTotal += 1 if self.mWalls[y-1][x-1] == '#' else 0
        wallTotal += 1 if self.mWalls[y-1][x] == '#' else 0
        wallTotal += 1 if self.mWalls[y-1][x+1] == '#' else 0

        # Check Sides
        wallTotal += 1 if self.mWalls[y][x-1] == '#' else 0
        wallTotal += 1 if self.mWalls[y][x+1] == '#' else 0

        # Check Bottom
        wallTotal += 1 if self.mWalls[y+1][x-1] == '#' else 0
        wallTotal += 1 if self.mWalls[y+1][x] == '#' else 0
        wallTotal += 1 if self.mWalls[y+1][x+1] == '#' else 0

        return wallTotal

    def Corrode( self , tolerance ):
        """ Corrode out walls with four or less walls touching them. """
        for row in range( self.mRows ):
            for col in range( self.mColumns ):
                if( row > 0 and row < self.mRows -1 ) and ( col > 0 and col < self.mColumns -1 ):
                    if( self.GetWallTouchingCount( col , row ) < tolerance ):
                        self.mWalls[ row ][ col ] = ' ';
                    else:
                        None
